<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            力扣220th周赛 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><style>mjx-container[jax="SVG"] {
  direction: ltr;
}

mjx-container[jax="SVG"] > svg {
  overflow: visible;
}

mjx-container[jax="SVG"][display="true"] {
  display: block;
  text-align: center;
  margin: 1em 0;
}

mjx-container[jax="SVG"][justify="left"] {
  text-align: left;
}

mjx-container[jax="SVG"][justify="right"] {
  text-align: right;
}

g[data-mml-node="merror"] > g {
  fill: red;
  stroke: red;
}

g[data-mml-node="merror"] > rect[data-background] {
  fill: yellow;
  stroke: none;
}

g[data-mml-node="mtable"] > line[data-line] {
  stroke-width: 70px;
  fill: none;
}

g[data-mml-node="mtable"] > rect[data-frame] {
  stroke-width: 70px;
  fill: none;
}

g[data-mml-node="mtable"] > .mjx-dashed {
  stroke-dasharray: 140;
}

g[data-mml-node="mtable"] > .mjx-dotted {
  stroke-linecap: round;
  stroke-dasharray: 0,140;
}

g[data-mml-node="mtable"] > svg {
  overflow: visible;
}

[jax="SVG"] mjx-tool {
  display: inline-block;
  position: relative;
  width: 0;
  height: 0;
}

[jax="SVG"] mjx-tool > mjx-tip {
  position: absolute;
  top: 0;
  left: 0;
}

mjx-tool > mjx-tip {
  display: inline-block;
  padding: .2em;
  border: 1px solid #888;
  font-size: 70%;
  background-color: #F8F8F8;
  color: black;
  box-shadow: 2px 2px 5px #AAAAAA;
}

g[data-mml-node="maction"][data-toggle] {
  cursor: pointer;
}

mjx-status {
  display: block;
  position: fixed;
  left: 1em;
  bottom: 1em;
  min-width: 25%;
  padding: .2em .4em;
  border: 1px solid #888;
  font-size: 90%;
  background-color: #F8F8F8;
  color: black;
}

foreignObject[data-mjx-xml] {
  font-family: initial;
  line-height: normal;
  overflow: visible;
}

.MathJax path {
  stroke-width: 3;
}

mjx-container[display="true"] {
  overflow: auto hidden;
}

mjx-container[display="true"] + br {
  display: none;
}
</style><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">力扣220th周赛</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2020-12-29 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/LeetCode/">LeetCode</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>1.6k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>7 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <blockquote>
<p>好久没写LeetCode的题了，来补一下<a class="link" target="_blank" rel="noopener" href="https://leetcode-cn.com/contest/weekly-contest-220/">220周赛<i class="fas fa-external-link-alt"></i></a>的T3和T4</p>
</blockquote>
<h2 id="1696-跳跃游戏-VI"><a href="#1696-跳跃游戏-VI" class="headerlink" title="1696. 跳跃游戏 VI"></a><a class="link" target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/jump-game-vi/">1696. 跳跃游戏 VI<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>中等</strong></p>
<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 和一个整数 <code>k</code> 。</p>
<p>一开始你在下标 <code>0</code> 处。每一步，你最多可以往前跳 <code>k</code> 步，但你不能跳出数组的边界。也就是说，你可以从下标 <code>i</code> 跳到 <code>[i + 1， min(n - 1, i + k)]</code> <strong>包含</strong> 两个端点的任意位置。</p>
<p>你的目标是到达数组最后一个位置（下标为 <code>n - 1</code> ），你的 <strong>得分</strong> 为经过的所有数字之和。</p>
<p>请你返回你能得到的 <strong>最大得分</strong> 。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line">输入：nums = [<span class="number">1</span>,<span class="number">-1</span>,<span class="number">-2</span>,<span class="number">4</span>,<span class="number">-7</span>,<span class="number">3</span>], k = <span class="number">2</span></span><br><span class="line">输出：<span class="number">7</span></span><br><span class="line">解释：你可以选择子序列 [<span class="number">1</span>,<span class="number">-1</span>,<span class="number">4</span>,<span class="number">3</span>] （上面加粗的数字），和为 <span class="number">7</span> 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line">输入：nums = [<span class="number">10</span>,<span class="number">-5</span>,<span class="number">-2</span>,<span class="number">4</span>,<span class="number">0</span>,<span class="number">3</span>], k = <span class="number">3</span></span><br><span class="line">输出：<span class="number">17</span></span><br><span class="line">解释：你可以选择子序列 [<span class="number">10</span>,<span class="number">4</span>,<span class="number">3</span>] （上面加粗数字），和为 <span class="number">17</span> 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line">输入：nums = [<span class="number">1</span>,<span class="number">-5</span>,<span class="number">-20</span>,<span class="number">4</span>,<span class="number">-1</span>,<span class="number">3</span>,<span class="number">-6</span>,<span class="number">-3</span>], k = <span class="number">2</span></span><br><span class="line">输出：<span class="number">0</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>  1 &lt;= nums.length, k &lt;= 10<sup>5</sup></li>
<li>  -10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></li>
</ul>
<h3 id="解法一"><a href="#解法一" class="headerlink" title="解法一"></a>解法一</h3><p>递推公式很容易得到，先来一发暴力解法，不出意料的T了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//1 2 3 4 5 k=2</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxResult</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> k)</span> </span>{</span><br><span class="line">    <span class="keyword">int</span> n = nums.length;</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    dp[<span class="number">0</span>] = nums[<span class="number">0</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; n; i++) {</span><br><span class="line">        dp[i] = -<span class="number">0x3f3f3f3f</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = i-<span class="number">1</span>; i-j &lt;= k &amp;&amp; j &gt;= <span class="number">0</span>; j--) {</span><br><span class="line">            dp[i] = Math.max(dp[j]+nums[i], dp[i]);</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">return</span> dp[n-<span class="number">1</span>];</span><br><span class="line">}</span><br></pre></td></tr></table></figure>

<h3 id="解法二"><a href="#解法二" class="headerlink" title="解法二"></a>解法二</h3><p>其实这题想了挺久的，主要是没想到T3会用到单调队列去优化dp，很巧的是这个单调队列优化这个知识点我刚刚在yxc那边学了一点，那个题目相对这题会复杂很多，是多重背包的问题。然后我就感觉这个题好像也可以用单调队列来优化，然后就试了一发，然后就AC了😁</p>
<blockquote>
<p>这里也可以借助其他的数据结构，比如线段树，st表，优先队列什么的去维护连续的大小为k的区间的最大值，这里我就不写了</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//1 2 3 4 5 k=2</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxResult</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> k)</span> </span>{</span><br><span class="line">    <span class="keyword">int</span> n = nums.length;</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    dp[<span class="number">0</span>] = nums[<span class="number">0</span>];</span><br><span class="line">    <span class="comment">//dp[i]   = Max(       dp[i-1], dp[i-2], dp[i-3],... dp[i-k+1], dp[i-k])</span></span><br><span class="line">    <span class="comment">//dp[i+1] = Max(dp[i], dp[i-1], dp[i-2], dp[i-3],... dp[i-k+1])</span></span><br><span class="line">    <span class="comment">//dp[i] --&gt; dp[i+1] 滑动窗口最大值</span></span><br><span class="line">    LinkedList&lt;<span class="keyword">int</span>[]&gt; queue = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; n; i++) {</span><br><span class="line">        <span class="keyword">while</span> (!queue.isEmpty() &amp;&amp; dp[i-<span class="number">1</span>] &gt; queue.getLast()[<span class="number">0</span>]) {</span><br><span class="line">            queue.removeLast();</span><br><span class="line">        }</span><br><span class="line">        <span class="keyword">if</span> (!queue.isEmpty() &amp;&amp; i-queue.getFirst()[<span class="number">1</span>] &gt;= k) {</span><br><span class="line">            queue.removeFirst();</span><br><span class="line">        }</span><br><span class="line">        <span class="comment">//这里也可以在队列中只存dp值的坐标，简化代码</span></span><br><span class="line">        queue.addLast(<span class="keyword">new</span> <span class="keyword">int</span>[]{dp[i-<span class="number">1</span>], i});</span><br><span class="line">        dp[i] = queue.getFirst()[<span class="number">0</span>]+nums[i];</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">return</span> dp[n-<span class="number">1</span>];</span><br><span class="line">}</span><br></pre></td></tr></table></figure>

<h2 id="1697-检查边长度限制的路径是否存在"><a href="#1697-检查边长度限制的路径是否存在" class="headerlink" title="1697. 检查边长度限制的路径是否存在"></a><a class="link" target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/checking-existence-of-edge-length-limited-paths/">1697. 检查边长度限制的路径是否存在<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>困难</strong></p>
<p>给你一个 <code>n</code> 个点组成的无向图边集 <code>edgeList</code> ，其中edgeList[i] = [u<sub style="display: inline;">i</sub>, v<sub style="display: inline;">i</sub>, dis<sub style="display: inline;">i</sub>] 表示点 u<sub style="display: inline;">i</sub><code> 和点 </code>v<sub style="display: inline;">i</sub> 之间有一条长度为 dis<sub style="display: inline;">i</sub> 的边。请注意，两个点之间可能有超过一条边。</p>
<p>给你一个查询数组<code>queries</code> ，其中 queries[j] = [p<sub style="display: inline;">j</sub>, q<sub style="display: inline;">j</sub>, limit<sub style="display: inline;">j</sub>] ，你的任务是对于每个查询 queries[j] ，判断是否存在从 p<sub style="display: inline;">j</sub> 到 q<sub style="display: inline;">j</sub>的路径，且这条路径上的每一条边都 <strong>严格小于</strong> limit<sub style="display: inline;">j</sub>。</p>
<p>请你返回一个 <strong>布尔数组</strong><code>answer</code>，其中<code>answer.length == queries.length</code> ，当 <code>queries[j]</code> 的查询结果为 <code>true</code> 时， <code>answer</code> 第<code>j</code> 个值为<code>true</code>，否则为 <code>false</code> 。</p>
<p><strong>示例 1：</strong></p>
<p><img lazyload="" src="/images/loading.svg" data-src="https://i.loli.net/2020/12/30/WiZjdPCsFca4JlE.png"></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line">输入：n = <span class="number">3</span>, edgeList = [[<span class="number">0</span>,<span class="number">1</span>,<span class="number">2</span>],[<span class="number">1</span>,<span class="number">2</span>,<span class="number">4</span>],[<span class="number">2</span>,<span class="number">0</span>,<span class="number">8</span>],[<span class="number">1</span>,<span class="number">0</span>,<span class="number">16</span>]], queries = [[<span class="number">0</span>,<span class="number">1</span>,<span class="number">2</span>],[<span class="number">0</span>,<span class="number">2</span>,<span class="number">5</span>]]</span><br><span class="line">输出：[<span class="literal">false</span>,<span class="literal">true</span>]</span><br><span class="line">解释：上图为给定的输入数据。注意到 <span class="number">0</span> 和 <span class="number">1</span> 之间有两条重边，分别为 <span class="number">2</span> 和 <span class="number">16</span> 。</span><br><span class="line">对于第一个查询，<span class="number">0</span> 和 <span class="number">1</span> 之间没有小于 <span class="number">2</span> 的边，所以我们返回 <span class="literal">false</span> 。</span><br><span class="line">对于第二个查询，有一条路径（<span class="number">0</span> -&gt; <span class="number">1</span> -&gt; <span class="number">2</span>）两条边都小于 <span class="number">5</span> ，所以这个查询我们返回 <span class="literal">true</span> 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<p><img lazyload="" src="/images/loading.svg" data-src="https://i.loli.net/2020/12/30/TRQdGcei1S8UX9k.png"></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line">输入：n = <span class="number">5</span>, edgeList = [[<span class="number">0</span>,<span class="number">1</span>,<span class="number">10</span>],[<span class="number">1</span>,<span class="number">2</span>,<span class="number">5</span>],[<span class="number">2</span>,<span class="number">3</span>,<span class="number">9</span>],[<span class="number">3</span>,<span class="number">4</span>,<span class="number">13</span>]], queries = [[<span class="number">0</span>,<span class="number">4</span>,<span class="number">14</span>],[<span class="number">1</span>,<span class="number">4</span>,<span class="number">13</span>]]</span><br><span class="line">输出：[<span class="literal">true</span>,<span class="literal">false</span>]</span><br><span class="line">解释：上图为给定数据。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>  2 &lt;= n &lt;= 10<sup>5</sup></li>
<li>  1 &lt;= edgeList.length, queries.length &lt;= 10<sup>5</sup></li>
<li>  edgeList[i].length == 3</li>
<li>  queries[j].length == 3</li>
<li>  0 &lt;= u<sub style="display: inline;">i</sub>, v<sub style="display: inline;">i</sub>, p<sub style="display: inline;">j</sub>, q<sub style="display: inline;">j</sub> &lt;= n - 1</li>
<li>  u<sub style="display: inline;">i</sub> != v<sub style="display: inline;">i</sub></li>
<li>  p<sub style="display: inline;">j</sub> != q<sub style="display: inline;">j</sub></li>
<li>  1 &lt;= dis<sub style="display: inline;">i</sub>, limit<sub style="display: inline;">j</sub> &lt;= 10<sup>9</sup></li>
<li>  两个点之间可能有 <strong>多条</strong> 边。</li>
</ul>
<h3 id="解法一-1"><a href="#解法一-1" class="headerlink" title="解法一"></a>解法一</h3><p>看到了评论区的一句提示然后写出了下面的解法，后来看题解区大佬科普这种类型的题目属于<a class="link" target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/checking-existence-of-edge-length-limited-paths/solution/jie-zhe-ge-wen-ti-ke-pu-yi-xia-shi-yao-j-pn1b/">离线算法<i class="fas fa-external-link-alt"></i></a>，其实核心的思想就是，对查询的limit和边权值进行排序，然后从小query的limit开始，将edge权值不大于limit的都丢到并查集里面，然后查询一下就行了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">int</span>[] parent;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> a)</span> </span>{</span><br><span class="line">    <span class="keyword">if</span> (parent[a] == a) {</span><br><span class="line">        <span class="keyword">return</span> a;</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">return</span> parent[a] = find(parent[a]);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">union</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span> </span>{</span><br><span class="line">    <span class="keyword">int</span> pa = find(a);</span><br><span class="line">    <span class="keyword">int</span> pb = find(b);</span><br><span class="line">    <span class="keyword">if</span> (pa == pb) <span class="keyword">return</span>;</span><br><span class="line">    parent[pa] = pb; </span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Pair</span> </span>{</span><br><span class="line">    <span class="keyword">int</span> p, q;</span><br><span class="line">    <span class="keyword">int</span> limit;</span><br><span class="line">    <span class="keyword">int</span> idx;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Pair</span><span class="params">(<span class="keyword">int</span> p, <span class="keyword">int</span> q, <span class="keyword">int</span> limit, <span class="keyword">int</span> idx)</span> </span>{</span><br><span class="line">        <span class="keyword">this</span>.p = p;</span><br><span class="line">        <span class="keyword">this</span>.q = q;</span><br><span class="line">        <span class="keyword">this</span>.limit = limit;</span><br><span class="line">        <span class="keyword">this</span>.idx = idx;</span><br><span class="line">    }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">boolean</span>[] distanceLimitedPathsExist(<span class="keyword">int</span> n, <span class="keyword">int</span>[][] edge, <span class="keyword">int</span>[][] q) {</span><br><span class="line">    parent = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) parent[i] = i;</span><br><span class="line">    <span class="keyword">boolean</span>[] res = <span class="keyword">new</span> <span class="keyword">boolean</span>[q.length];</span><br><span class="line">    Pair[] query = <span class="keyword">new</span> Pair[q.length];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; q.length; i++) {</span><br><span class="line">        query[i] = <span class="keyword">new</span> Pair(q[i][<span class="number">0</span>], q[i][<span class="number">1</span>], q[i][<span class="number">2</span>], i);</span><br><span class="line">    }</span><br><span class="line">    Arrays.sort(edge, (e1, e2)-&gt;e1[<span class="number">2</span>]-e2[<span class="number">2</span>]);</span><br><span class="line">    Arrays.sort(query, (q1, q2)-&gt;q1.limit-q2.limit);</span><br><span class="line">    <span class="keyword">int</span> j = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; query.length; i++) {</span><br><span class="line">        <span class="keyword">while</span> (j &lt; edge.length &amp;&amp; edge[j][<span class="number">2</span>] &lt; query[i].limit) {</span><br><span class="line">            union(edge[j][<span class="number">0</span>], edge[j][<span class="number">1</span>]);</span><br><span class="line">            j++;</span><br><span class="line">        }</span><br><span class="line">        res[query[i].idx] = find(query[i].p) == find(query[i].q);</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>看了大佬们的代码后稍微做了下点简化</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">int</span>[] parent;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> a)</span> </span>{</span><br><span class="line">    <span class="keyword">if</span> (parent[a] == a) <span class="keyword">return</span> a;</span><br><span class="line">    <span class="keyword">return</span> parent[a] = find(parent[a]);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">union</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span> </span>{</span><br><span class="line">    <span class="keyword">int</span> pa = find(a);</span><br><span class="line">    <span class="keyword">int</span> pb = find(b);</span><br><span class="line">    <span class="keyword">if</span> (pa == pb) <span class="keyword">return</span>;</span><br><span class="line">    parent[pa] = pb; </span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">boolean</span>[] distanceLimitedPathsExist(<span class="keyword">int</span> n, <span class="keyword">int</span>[][] edge, <span class="keyword">int</span>[][] q) {</span><br><span class="line">    parent = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    <span class="keyword">int</span> qlen = q.length;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) parent[i] = i;</span><br><span class="line">    <span class="keyword">boolean</span>[] res = <span class="keyword">new</span> <span class="keyword">boolean</span>[qlen];</span><br><span class="line">    <span class="comment">//记录query排序后的id</span></span><br><span class="line">    Integer[] qid = <span class="keyword">new</span> Integer[qlen];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; qlen; i++) qid[i] = i;</span><br><span class="line">    Arrays.sort(edge, (e1, e2)-&gt;e1[<span class="number">2</span>]-e2[<span class="number">2</span>]);</span><br><span class="line">    Arrays.sort(qid, (i1, i2)-&gt;q[i1][<span class="number">2</span>]-q[i2][<span class="number">2</span>]);</span><br><span class="line">    <span class="keyword">int</span> j = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; qlen; i++) {</span><br><span class="line">        <span class="keyword">while</span> (j &lt; edge.length &amp;&amp; edge[j][<span class="number">2</span>] &lt; q[qid[i]][<span class="number">2</span>]) {</span><br><span class="line">            union(edge[j][<span class="number">0</span>], edge[j][<span class="number">1</span>]);</span><br><span class="line">            j++;</span><br><span class="line">        }</span><br><span class="line">        res[qid[i]] = find(q[qid[i]][<span class="number">0</span>]) == find(q[qid[i]][<span class="number">1</span>]);</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：力扣220th周赛</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2020-12-29 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2020/12/29/8e50a4df/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2020/12/31/ac62073a/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">0202年度总结</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2020/11/24/8f4e877d/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">Lc1621.大小为K的不重叠线段的数目</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2020/12/29/8e50a4df/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#1696-%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F-VI"><span class="nav-number">1.</span> <span class="nav-text">1696. 跳跃游戏 VI</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%A7%A3%E6%B3%95%E4%B8%80"><span class="nav-number">1.1.</span> <span class="nav-text">解法一</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%A7%A3%E6%B3%95%E4%BA%8C"><span class="nav-number">1.2.</span> <span class="nav-text">解法二</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1697-%E6%A3%80%E6%9F%A5%E8%BE%B9%E9%95%BF%E5%BA%A6%E9%99%90%E5%88%B6%E7%9A%84%E8%B7%AF%E5%BE%84%E6%98%AF%E5%90%A6%E5%AD%98%E5%9C%A8"><span class="nav-number">2.</span> <span class="nav-text">1697. 检查边长度限制的路径是否存在</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%A7%A3%E6%B3%95%E4%B8%80-1"><span class="nav-number">2.1.</span> <span class="nav-text">解法一</span></a></li></ol></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
